1. Field of the Invention
The present invention relates to methods and apparatuses for decoding turbo codes and similar codes used in communications systems. In connection with such decoding, the present invention also provides improved techniques for interleaving and de-interleaving. Such interleaving and de-interleaving techniques also may be used in various other applications in communications systems and other systems.
2. Description of the Related Art
In order to reduce the likelihood of information loss due to fading, noise and other communication channel imperfections, it has become common in the design of communications systems to code digital signals to be transmitted. Such coding typically involves spreading the information contained in the data bits across a greater number of data bits. The simplest form of such coding is repetition coding in which each bit is simply repeated N times, N being an integer. However, in practice it is more common to use convolutional encoding, in which the value of each output symbol is formed on the basis of multiple input bits.
In any event, once such information spreading has been completed, the resulting symbols are typically interleaved, so as to insure that correlated information bits are not immediately adjacent to each other in the time domain. By so interleaving, the effects of bursts of noise or fading are distributed over multiple input bits. The end result is that the probability that any particular input bit cannot be recovered at the receiving end is significantly reduced, meaning more accurate reproduction at the receiving side of the communication channel.
One type of encoding that recently has become prevalent is turbo coding, such as the turbo coding defined in the IS-2000 standard. A simplified block diagram of a system 20 for implementing IS-2000 turbo coding is illustrated in FIG. 1. As shown in FIG. 1, input into system 20 is a sequence of information bits 22 to be communicated. Information bits 22 are supplied directly to convolutional encoder 24 and are supplied to convolutional encoder 28 via turbo interleaver 26. Encoders 24 and 28 are identical. Turbo interleaver 26 is a block interleaver, meaning that it interleaves bits in fixed-length segments (or blocks), with the bits of each such block being interleaved independently of any other block, but with the interleaving pattern being identical for all blocks. The precise details of the operation of interleaver 26 and encoders 24 and 28 are not critical to the present invention and therefore are not discussed here. However, each encoder outputs three symbols for each input bit. Thus, encoder 24 outputs symbols X, Y0 and Y1 and encoder 28 outputs symbols X′, Y0′ and Y1′. Typically, X′ is simply discarded and only the X, Y0, Y1, Y0′ and Y1′ symbols (the turbo code) are transmitted, with the possible puncture of some of these symbols to accommodate different (e.g., higher) coding rates.
Specifically, the turbo code generated in the foregoing manner is first provided to channel interleaver and symbol puncturer 30, which interleaves the coded output symbols and also punctures certain of the symbols to insert power control signals and/or to accommodate various coding rates. Thereafter, the resulting symbols can be processed for transmission, such as by performing quadrature phase-shift keying.
A system 50 for performing straightforward decoding of the symbols generated by system 20 is illustrated in FIG. 2. Initially, channel de-interleaver 52 zeroes the symbols punctured by channel interleaver and symbol puncturer 30 and then de-interleaves the interleaving performed by channel interleaver and symbol puncturer 30. For each input bit k, the received symbols X, Y0 and Y1, together with a feedback signal L(uk), are input into a posteriori probability (APP) decoder 54. On the first pass, L(uk) is zero for all values of k. Upon completion of its decoding operation, APP decoder 54 outputs a soft value {tilde over (L)}(ûk) for each value of k. {tilde over (L)}(ûk) is then interleaved with interleaver 56 to provide L(un) which is then input into APP decoder 58, together with all Y0′ and Y1′ for the current block. The output of APP decoder 58, {tilde over (L)}(ûn), is then de-interleaved in de-interleaver 60. Finally, the output of de-interleaver 60, L(uk), is input into APP decoder 54, together with all X, Y0 and Y1 for the current block, for the next pass of processing to be performed by system 50. The foregoing process is repeated for multiple iterations. In this regard, it is noted that channel de-interleaver 52 makes available all X, Y0, Y1, Y0′ and Y1′ for each original input bit in the current block. After a number of iterations, as described above, the values {tilde over (L)}(ûk) and L(uk) are added together for each input bit k in adder 62. The output of adder 62, L(ûk), is then input into hard decision module 64 to provide a final decision for each bit. Typically, hard decision module 64 is implemented as a threshold detector.